package insertsort;



public class Shell {

    // 希尔排序
    public void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            sort(arr, gap);
        }
    }

    /**
     * 时间复杂度：O(n1.25) 到 O(1.6*n1.25)
     * 空间复杂度：O(1)
     * 稳定性： 不稳定
     * @param arr 待排序的数组
     * @param gap 增量  分为几组排序；
     */
    private void sort(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arr[j] > temp) {
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = temp;
        }
    }
}
